package internal.merge;

/**
 * @描述：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
 * @效率：归并排序的最好、最坏和平均时间复杂度都是O(nlogn)，而空间复杂度是O(n)，比较次数介于(nlogn)/2和(nlogn)-n+1，赋值操作的次数是(2nlogn)。因此可以看出，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。
 * @适用场合：归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，由于它需要一个额外的数组，因此需要比堆排序多一些内存空间。
 * @作者：hongxingfan
 * @时间：2014年9月5日 下午2:34:31
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] datas = { 9, 4, 1, 8, 7, 5, 2, 0, 3, 4, 6 };

        // 归并排序
        mergeSort(datas, 0, datas.length - 1);

        // 输出结果
        for (int data : datas)
            System.out.print(data + " ");
        System.out.println();
    }

    // 递归是一种编程思想
    public static void mergeSort(int[] datas, int low, int high) {
        // if是递归的出口
        if (low < high) {
            int mid = (low + high) / 2;
            mergeSort(datas, low, mid);
            mergeSort(datas, mid + 1, high);
            merge(datas, low, mid, high);
        }
    }

    public static void merge(int[] datas, int low, int mid, int high) {
        int[] tmp = new int[high - low + 1];
        int index = 0;
        int i = low;
        int j = mid + 1; // 分段归并，不让同一个元素即属于前一段又属于后一段
        // 比较是low指针迁移mid不动j前移
        while (low <= mid && high >= j) {
            if (datas[low] < datas[j]) {
                tmp[index++] = datas[low++];
            } else {
                tmp[index++] = datas[j++];
            }
        }
        while (low <= mid) {
            tmp[index++] = datas[low++];
        }
        while (j < high) {
            tmp[index++] = datas[j++];
        }
        for (int ii = 0; ii < tmp.length; ii++) {
            datas[i++] = tmp[ii];
        }
    }
}
